Almathera Ten Pack 3: CDPD 3/Almathera Ten on Ten - Disc 3: CDPD3.iso/scope/151-175/scopedisk152/atree/numbering_tutorial

Text File | 1995-03-19 | 19KB | 515 lines

The Binary and Hexadecimal Numbering Systems

The binary and hexadecimal numbering systems are very important in computer
science and anyone wishing to advance their knowledge of the subject to
attain a deeper understanding of computers must learn them. In order to
understand and use the Atree Sector Editor, an understanding of at least
the hexadecimal numbering system is necessary. This tutorial is presented
to assist users in fully exploiting the power of Atree and its secotr editor.

The binary and hexadecimal numbering systems are just two of an infinite
number of possible numbering systems. And all numbering systems have
the same properties. Once these properties are understood for numbering
systems in general it becomes very easy to understand any numbering system
and even design your own. This tutorial therefore is designed to bring you to
an understanding of numbering systems in general first. Then our discussion of
the binary and hexadecimal systems will be a snap.

We will start with what is undoubtedly familiar to everyone -- the base 10
numbering system. This is the counting or numbering system we all learned
in grammar school and use almost daily without thinking about it much.

In the base 10 system there are ten digits -- 1 thru 9, and 0. This is a
very significant fact. In the base 5 system there are 5 digits -- 1 thru 4,
and 0. In the base 8 system there are 8 digits, 1 thru 7, and 0.

The general rule is that in the base x system, there are x digits. There
are 1 to x-1 digits which are related to each other by the property that
each succeeding digit is equal to the former digit plus one. And there is
always a digit representing the concept of nothing -- 0.

With only ten digits, how do we count or number greater than 9? Well, you
all probably remember from your grammar school years that we organize
digits in columns -- remember the one's column, the ten's column, the
hundred's column?

A number like 728 means 8 one's, two ten's, and 7 hundred's. To obtain the
value of 728, we actually multiply 8 times 1, and add it to 2 times 10, and
then add this result to 7 times one hundred.

Notice that one, ten and one-hundred are all powers of ten, the base of our
numbering system. In fact, that's why 10 is called the base. One is 10 to
the power 0; 10 is 10 to the power 1, and one-hundred is 10 to the power 2.

Each column of a number represents another power of 10. Thus, we can have a
thousand's column (10 to the third power, or ten cubed), and a
ten-thousand's column (10 to the fourth power), etc.

Now think about how we count. When we get up to 9 in the one's column, we
then write "10" as the next number. When we get up to 19, we then write
"20" as the next number. When we get to 99 we then write "100" as the next
number.

Think of the mileage indicator on your car. It starts at the factory with
all columns set to 0's. Each column is represented by a small cylinder with
the numbers 1,2,3,4,5,6,7,8,9,0 written evenly around the outer edge. Each
cylinder does nothing but go around in circles repeatedly as you drive. But
the cylinder's are interrelated so that every time a given cylinder
completes one cycle and returns to "0", the cylinder immediately to the
left then rolls to its next digit.

Now let's rethink what we have said so far using a base 5 system.

We will have only five digits; 1 thru 4 and 0. We will still have our one's,
ten's, hundred's column, etc., but the values of these columns will not be
powers of ten -- they will be powers of five, the base. The one's column will
have a value of 5 to the 0 power (or 1), the ten's column will have a value
of 5 to the power of 1 (or 5), the hundred's column will have a value of 5
to the power of 2 (or 25), and so on.

Note that in the base 5 system, you cannot have a number like 732 -- the
seven is not defined. You can have numbers like 423, 122, 444, 1000. But
they won't mean the same thing as in the base 10 system.

In the base ten system, 444 means 4 hundreds, plus 4 tens, plus 4 ones. But
in the base five system, 444 means 4 twenty-fives (which would be the
equivalent of 100 in the base ten system), 4 fives (which would be the
equivalent of 20 in the base ten system), and 4 ones (which has the same
value in both systems). So, 444 in the base five system is equivalent to
124 in the base ten system.

Study closely the parallel method of calculating the value of 444 in the
base 10 system on the one hand and in the base 5 system on the other:

Base 10 value of 444 =

4 X 10 X 10 = 400
4 X 10      =  40
4 X 1       =   4
TOTAL       = 444

Base 5 value of 444 =

4 X 5 X 5 = 100
4 X 5     =  20
4 X 1     =   4
TOTAL     = 124


What would 292 (base 10) be in the base 5 system? Well, obviously what we
would like to have as our end result is a base five number such that when
we do the kind of conversion we did on 444 above we end up with 292 as its
base ten equivalent. This number we are shooting for will have digits in it
representing powers of five. Let's look at the powers of five up to the
fourth power:

5 to the 0 = 1
5 to the 1 = 5
5 to the 2 = 25
5 to the 3 = 125
5 to the 4 = 625

What we want to do is represent 292 as a sum of numbers which are multiples
of powers of five. It is easy to intuitively notice in this case that 292 can
be represented as:

(a)        2 X 125 + 1 X 25 + 3 X 5 + 2 X 1

This is equivalent to:

(b)        250 + 25 + 15 + 2

And this adds up to 292.

Moreover, (a) above is the key to our conversion; 125 represents the base
five "thousands" column; 25 is the base five "hundreds" column, and 5 is
the base five "tens" column. So the base five number we are looking for is
2132.

To double check our work, we can convert the base five number 2132 into its
base ten equivalent. The 2 represents 2 times five to the third power
(which is 250), and the 1 represents 1 times five to the power of 2 (which
is 25), and the 3 is 3 times the power of five to the power of 1 (which is
15), and finally add in the 2; all this gives 292.

Let's try converting the base ten number 2398 into its base five
equivalent.

Remember, what we want to do is represent this number as the sum of a series
of multiples of powers of five.

There is a very systematic and easy to follow technique for doing this.

The first question you ask is,  "What is the largest power of five that will
divide the number with a result greater than one?"

In our little table of powers of five above, we note that five to the power
of two (25) divides the number with a result larger than one, but it is not
the largest power of five that does so. Five to the power of three (125)
also divides 2398 with a result larger than one, but so does five to the
power of 4 (625). Five to the power of 5 (3125) does not divide 2398 with a
result larger than one, so therefore five to the power of 4 (625) is the
answer to our first question -- it is the largest power of five that
divides our number, 2398, with a result that is larger than one.

The next step is to actually do the division and determine the remainder.

In this case, 2398 divided by 625 yields 3 with a remainder of 523.

We may now write 2398 as:

(a) 3 X 625 + 523  = 2398

Now, we deal with the remainder of 523 and divide it by the next smaller
power of five. 625 is five to the fourth power, so the next smaller is
therefore five cubed, which is 125. 523 divided by 125 yields 4 with a
remainder of 23.

523 can therefore be represented as:

(b) 4 X 125 + 23 = 523.

Substituting (b) for the 523 in (a), we get:

(c) 3 X 625 + 4 X 125 + 23 = 2398


Now we look at the remainder of 23. And we divide it by the next smaller
power of five. The next smaller power of five is now 25. 23 divided by 25
yields a result of 0 with a remainder of 23. So we now re-write line (c) above as:

(d) 3 X 625 + 4 X 125 + 0 X 25 + 23 = 2398

We again look at the remainder of 23 and again we divide by the next
smaller power of five, which this time is 5. 23 divided by 5 yields 4 with
a remainder of three. So we can re-write (d) above as:

(e) 3 X 625 + 4 X 125 + 0 X 25 + 4 X 5 + 3 = 2398

Our remainder of 3 is now exactly divisible by the next smaller (and last)
power of five (which is five to the 0 = 1).

It is now obvious that the base five equivalent of the base ten number, 2398,
is 34043.

What we did to get 34043 was to simply take the digits that we needed to
multiply with the decreasing powers of 5 (625, 125, 25, 5, 1) to get our
base 10 number.



The Binary Number System


What is called the binary number system simply has a base of 2. That means
there are only two digits -- 0 and 1.

Let's take a four digit binary number and start counting -- remember the
cylinder process:



Base 10                    Binary


0                                0000
1                                0001
2                                0010
3                                0011
4                                0100
5                                0101
6                                0110
7                                0111
8                                1000
9                                1001
10                            1010
11                            1011
12                            1100
13                            1101
14                            1110
15                            1111


Since we are dealing with the base 2 system, the columns from right to left
represent increasing powers of 2, starting with 2 to the power of 0 = 1, then
2 to the power of 1 = 2, then 2 to the power of 2 = 4, then 2 to the power of
3 = 8. The powers of 2 up to the 10th power are 1 ,2, 4, 8, 16, 32, 64, 128,
256, 512, 1024.

The binary representation of these powers of 2 would of course be:

--------------------------------------------------
Power of two     Binary number       Decimal value
--------------------------------------------------
            0            1                   =            1
            1            10                  =            2
            2                         100              =            4
            3            1000                =            8
            4            10000            =            16
            5            100000              =           32
            6            1000000          =           64
            7            10000000            =           128
            8            100000000      =            256
            9            1000000000     =           512
            10           10000000000    =          1024


Let's do some converting. What would the binary number 1011001101 be in decimal?

Let's first number the columns starting at the far right with the first column.
We will start numbering with "0" so that our column numbers represent the powers
of 2 we must use for the value in that column:

9 8 7 6 5 4 3 2 1 0
1 0 1 1 0 0 1 1 0 1


Now we can start calculating the decimal value of the binary number.

We simply calculate the decimal equivalent of the value of each of the
columns of the binary number. Since the columns that have a "0" in them
will always evaluate to "0", we can ignore them. The columns number of the
columns which have 1's in them are:

9
7
6
3
2
0

These represent the powers to which we have to raise the number 2 to
determine the decimal value. The decimal values corresponding to these values
of two are given in the small table above. We can rewrite the column numbers
now with the decimal values of each colum:

9   512
7   128
6    64
3     8
2     4
0     1

Now we add up the decimal values in the right hand column above to get
717.

What is the binary number whose decimal value is 946?

Using the table above, we see that 512 is the highest power of 2 that
divides 946 with a result greater than one. This value corresponds
to 2 to the power of 9. Therefore, we are dealing with a nine digit
binary number -- our result must have a value (either 0 or 1) in each
of the columns, 0 thru 9.

Let's write the number of these colums:

9 8 7 6 5 4 3 2 1 0


Now 512 divides 946 once with a remainder of 434. So we put a "1" below
the 9. Column 8 represents 2 to the power of 8 which is 256. 256 divides
434 once with a remainder of 178. So se can put a "1" below it too. Column
7 represents 2 to the power of 7 which is 128. 128 divides 178 once with a
remainder of 50. So we can put a "1" below it. Column 6 represents 64 and
64 does not divide 50 with a result greater than one. So se put a "0" in
column 6. Column 5 represents 32 and 32 divides 50 once with a remainder of
18. Se we can put a 1 in column 5. Column 4 represents 16. 16 divides 18 once
with a remainder of 2. So we put a "1" in column 4. Columns 3 and 2 represent
8 and 4 respectively and niether of these divides 2 more than once, so we put
0's in both column 3 and column 2. Column 1 represnets 2 and 2 divides 2 once
with a remainder of 0. So we put a 1 in column 1. Since the remainder is 0,
we put a 0 in column 0.

We end up with 1110110010 (base 2) = 946 (base 10).

Why are binary numbers so important to the study of computer science?

The reason is that a computer's memory is made up of hundreds of thousands, or
even millions, of tiny transistors. A transistor is an electronic component that
has two states -- it either acts to greatly restrict the flow of current through
it, or it acts to let the current flow quite freely. Hence it is spoken of as
being either "on" (allowing high current flow, hence high voltage), or "off"
(allowing low current flow, hence low voltage).

Obviously, the on/off or high/low states of transistors lend themselves to
binary interpretation -- 1 or 0.

You can string a number of transistors together and let each one represent
a column of a binary number. In fact, that's just what computer engineers
do. And the typical number of transistors so strucg together is 8. Hence,
a very standard computer number is an 8 digit (or 8 column, if you wish)
binary number.

An 8 digit binary number is called a byte. The digits or columns are of course
numbered 0 thru 7 (instead of 1 thru 8) so that the column number represents the
power of 2 that the column represents. Each column is called a bit. Thus, we speak
of bit 7, or bit 6, or the zero bit.

The low bit of a binary number is always bit zero. The high bit is always the
highest bit of the number. Thus, the high bit of a byte is bit 7. The low
bit is also referred to as the Least Siginificant Bit, or LSB. The high
bit is also referred to as the MSB; Most Siginificant Bit.

If the value of a bit is 1, the bit is said to be set. If it is 0, it is
said to be clear.

In the binary number 10110, the low bit is clear, the high bit is set. The
high bit is bit 4; bit 3 is clear, and bits one and two are set.

A byte can have values ranging from 00000000 to 11111111. The decimal
equivalent is 000 to 255. There are a total of 256 values (0 - 255).

In general, an x bit binary number has 2 to the power of x values,
ranging from 0 to (2 to the powers of x) - 1.

Thus, a byte, being an 8 bit binary number, has 2 to the power of 8
(256) values, ranging from 0 to 255. A 16 bit binary number has 2 to the
power of 16 (or 256 X  256 = 65,536) values, ranging from 0 to 65,535.

The first four bits of a byte are referred to as the low nibble; the last
four bits are referred to as the high nibble.

When we write decimal numbers, we conventionally use a comma every three
columns to make the number easier to comprehend. Spaces are typically used
for this purpose with binary numbers. Sometimes spaces are used between
the nibbles of bytes. Thus 10110011 is written as 1011 0011. Alternatively,
a space separates bytes in longer binary numbers. A 32 bit binary number
is thus frequently rendered as four bytes separated by spaces. Thus,

            10110011 01011100 10101111 00010010



The Hexadecimal Numbering System


Don't be alarmed by the name -- we are simply talking about a base 16
numbering system.

In the numbering systems we have looked at so far the base has always been
less than 10. We therefore needed less than 10 symbols to represent our
digits and we could therefore use the same ones we are familiar with from
the base 10 system (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0).

What do we do when we are dealing with number systems whose bases are larger
than 10?

We use all of the numbers from the base 10 system, and when we run out, we
use the letters of the alphabet.

Thus, the base 12 system would have 12 digits as follows:

                  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B.

The base 14 system would have 14 digits as follows:

                  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D.


And the base 16 (or hexadecimal) system would have 16 digits as follows:

                                    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.





In all of the above, the symbols A thru F have the decimal equivalent values
of 10 thru 15 respectively.

Let's convert the hexadecimal number A7C034F into its decimal equivalent.

First, let's determine the values of the columns. Our particular number
has 7 columns, 0 thru 6. And we are dealing with powers of 16, the base.
Let's write down the decimal values of these powers as follows:

Power of 16           Decimal Value

        0                                                1
        1                                                16
        2                                                256
        3                                                4096
        4                                                65536
        5                                                1048576
        6                                                16777216


Now we can re-write this table showing the digits of the hexadecimal number
in the correct places:

Power of 16           Decimal Value     hex digit

        0                                                1                                F
        1                                                16                            4
        2                                                256                            3
        3                                                4096                        0
        4                                                65536                        C
        5                                                1048576                    7
        6                                                16777216                A



We can write this table one more time. This time, we will include the
decimal values of the hex digits A thru F:

Power of 16           Decimal Value     hex digit  Dec value of hex

        0                                                1                                F                            15
        1                                                16                            4                             4
        2                                                256                            3                             3
        3                                                4096                        0                             0
        4                                                65536                        C                            12
        5                                                1048576                    7                             7
        6                                                16777216                A                            10



Now, to get the decimal value of our hex number all we have to do is
multiply the values in the "Decimal Value" column by the corresponding
values in the "Dec value of hex" column and add the results together.

The hexadecimal numbering system is very commonly used in computer science.
Why? Because it has a very close relationship to the base 2, or binary
numbering system.

This relationship becomes clear when we examine a table showing the binary
equivalent of the 16 hexadecimal digits.


                                    Hex Digit              Binary Equivalent

                                            0                                                    0000
                                            1                                                    0001
                                            2                                                    0010
                                            3                                                    0011
                                            4                                                    0100
                                            5                                                    0101
                                            6                                                    0110
                                            7                                                    0111
                                            8                                                    1000
                                            9                                                    1001
                                            A                                                    1010
                                            B                                                    1011
                                            C                                                    1100
                                            D                                                    1101
                                            E                                                    1110
                                            F                                                    1111



Notice that four bits of a binary digit correspond to one hexadecimal digit.
Therefore 8 bits correspond to two hex digits. A byte, in other words, can
be represented as two hexadecimal digits. And to translate quickly from one
to the other, all you need is the above table.

Thus, 11100011 in binary is E3 in hex. A5 is 10100101 in binary.

Learning to live comfortably with several numbering systems is a must
for those interested in geting below the surface level of computer
understanding. Playing with various numbering systems and playing with
converting values from one to another is a good way of developing your
comfort with them.